package com.zklh.leetcode.interviewTop150;

import java.util.*;

/**
 * 课程表II
 * author: tongnan
 * date: 2024/8/6
 */
public class Solution210 {

    /**
     * 这里使用深度优先搜索实现
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edges = buildGraph(numCourses, prerequisites);
        List<Integer> allPoints = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            allPoints.add(i);
        }
        edges.add(allPoints);
        Deque<Integer> deque = new LinkedList<>();
        int[] visited = new int[numCourses+1]; // 0 未访问，1 正在访问，2 已访问
        if (!dfs(edges.size()-1, edges, visited, deque)) {
            return new int[]{};
        }
        int[] res = new int[numCourses];
        deque.pop();
        for (int i = 0; i < numCourses; i++) {
            res[i] = deque.pop();
        }
        return res;
    }

    private boolean dfs(int i, List<List<Integer>> edges, int[] visited, Deque<Integer> deque) {
        if (visited[i] == 2) {
            return true;
        }
        if (visited[i] == 1) {
            return false;
        }
        visited[i] = 1;
        for (Integer j : edges.get(i)) {
            if (!dfs(j, edges, visited, deque)) {
                return false;
            }
        }
        visited[i] = 2;
        deque.push(i);
        return true;
    }

    private List<List<Integer>> buildGraph(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] pre : prerequisites) {
            edges.get(pre[1]).add(pre[0]);
        }
        return edges;
    }

    public static void main(String[] args) {
        Solution210 solution210 = new Solution210();
        int[] res = solution210.findOrder(4, new int[][]{{1,0},{2,0},{3,1},{3,2}});
        System.out.println(Arrays.toString(res));
    }
}
